package zuoshen_video;
import java.util.*;

import org.junit.Test;

import jdk.nashorn.api.tree.Tree;
import tree.Node;
import tree.TreeNode;
import tree.TreeUtils;

public class TreeProblems {
 
    //1.树的后序非递归
    class PostTraverse {

        // 方式一： 正常版
        public List<TreeNode> postOrder1(TreeNode root) {
            List<TreeNode> res = new ArrayList<>();
            TreeNode cur = root, last = null;//last记录上一轮被访问的节点
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || cur != null) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.peek(); //不能出栈
                if (cur.right != null && cur.right != last) {
                    cur = cur.right;
                } else {
                    //左右子树都访问过了，才能出栈
                    cur = stack.pop();
                    res.add(cur); //访问，并记录
                    last = cur;
                    cur = null; //设置为null，让接下来不会再次访问左节点
                }
            }
            return res;
        }

        //2.巧妙方法：将前序遍历变成 中 右 左 的形式，然后将访问结果逆序【借助第二个栈】
        public List<TreeNode> postOrder(TreeNode root) {
            List<TreeNode> res = new ArrayList<>();
            TreeNode cur = root;
            Stack<TreeNode> stack = new Stack<>();//逆转栈
            Stack<TreeNode> help = new Stack<>(); //主要依赖的遍历栈
            help.push(cur);

            while (!help.isEmpty()) {
                cur = help.pop();
                stack.push(cur); //暂存遍历结果【逆序】，代替遍历
                System.out.println(cur.val + ", ");
                if (cur.left != null) help.push(cur.left);
                if (cur.right != null) help.push(cur.right);
            }

            while (!stack.isEmpty()) {
                res.add(stack.pop());
            }
            return res;
        }
    }

    class PreAndNextInOrderNode {
        public Node preInOrderNode(Node cur) {
            Node node;
            if (cur.left != null) {
                node = cur.left;
                while (node.right != null) {
                    node = node.right;
                }
                return node; //左子树最右节点
            } else {
                node = cur;
                Node p = cur.parent;
                while (p != null && p.right != node) {
                    node = p;
                    p = p.parent;
                }
                return p; //返回以某个祖先为右子树的节点
            }
        } 

        public Node nextNode (Node cur){ //cur不为空
            if (cur.right != null) {
                Node node = cur.right;
               while (node.left != null) {
                   node = node.left;
               }
               return node; //返回右子树最左节点
            } else {
                //返回以某个祖先节点为左子树的节点
                Node p = cur.parent;
                Node node = cur;
                while (p != null && p.left != node) {
                    node = p;
                    p = p.parent;
                }
                return p;
            }
        }
    }

    class SerializeTree {
        //层序序列化【此序列化方法会多出一层的null节点】
        public String serializeByLeverOrder(TreeNode root) {
            if (root == null) return "null";
            TreeNode cur = root;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(cur);
            StringBuilder sb = new StringBuilder(cur.val + ",");
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (cur.left != null) {
                    sb.append(cur.left.val + ",");
                    queue.offer(cur.left);
                } else {
                    sb.append("null,");
                }
                if (cur.right != null) {
                    sb.append(cur.right.val + ",");
                    queue.offer(cur.right);
                } else {
                    sb.append("null,");
                }
            }
            return sb.toString();
        }

        public TreeNode deserializeByLevelOrder(String s) {
            String[] ss = s.split(",");
            if (ss.length == 1) return null; //若有节点，至少长度为3
            int idx = 0, left, right, len = ss.length;
            TreeNode root, cur;
            root = new TreeNode(Integer.parseInt(ss[0]));
            cur = root;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(cur);
            while (!queue.isEmpty()) {
                cur = queue.poll();
                left = idx * 2 + 1;
                right = idx * 2 + 2;
                if (left < len) {
                    if ("null".equals(ss[left])) {
                        cur.left = null;
                    } else {
                        cur.left = new TreeNode (Integer.parseInt(ss[left]));
                        queue.offer(cur.left);
                    }     
                }
                if (right < len) {
                    if ("null".equals(ss[right])) {
                        cur.right = null;
                    } else {
                        cur.right = new TreeNode (Integer.parseInt(ss[right]));
                        queue.offer(cur.right);
                    }     
                }
                idx++;
            }
            root.printTree();
            return root;
        }


        //前序序列化，其他序都是差不多的
        public String serializeByPreOrder(TreeNode root) {
            if (root == null) return "null";
            return root.val + "," + serializeByPreOrder(root.left) +"," + serializeByPreOrder(root.right);

        }
         public TreeNode deserializeByPreOrder(String s) {
            String[] ss = s.split(",");
            if (ss.length == 1) return null;
            idx = 0;
            return preOrderDeser(ss);
         }
         int idx;
         public TreeNode preOrderDeser(String[] ss) {
             if ("null".equals(ss[idx])) {
                idx++;
                return null;
             }
             TreeNode root = new TreeNode(Integer.parseInt(ss[idx++]));
             root.left = preOrderDeser(ss);
             root.right = preOrderDeser(ss);
             return root;
         }
         
    }

    class JuageTree {
        public boolean isFullBinaryTree(TreeNode root) {
            //层序遍历，找到起始的叶子结点或者非全节点，其后全是叶子结点
            if (root == null) return true;
            TreeNode cur = root;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(cur);
            boolean startCheckLeaf = false;

            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (cur.left == null || cur.right == null) {
                    //子节点存在空节点
                    if (cur.left == null && cur.right != null) return false; //左空右有，不是完全二叉树
                    else if (cur.right == null) {
                        if (startCheckLeaf && cur.left != null) return false;  //之前最后非叶节点已经出现，现在又冒出来一个，不是完全二叉树
                        else if (cur.left != null) queue.offer(cur.left);
                        //右子树为空，说明此时为最后一个非叶子节点     
                        startCheckLeaf = true;
                    }
                } else {
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
            }
            return true;
        }
    }

    class FullTreeCount {
        //不遍历所有节点，计算完全二叉树的节点数量
        public int countFullTreeNodes(TreeNode root) {
            if (root == null) return 0;
            //得到左、右子树高度
            int left = getSubTreeHeight(root.left), 
            right = getSubTreeHeight(root.right);
            int res = 1; //res当前只记录根节点数量
            if (left == right) {
                //左右子树高度相等，证明左子树必为满二叉树
                //左子树通过满二叉树公式计算[满二叉树公式：2^h - 1]
                res += (1 << left) - 1; //1左移left - 1 等价于 2^(left - 1) [1左移1位就是乘二，而起始为1节点必须为0次方，即左移0位]
                res += (countFullTreeNodes(root.right)); //递归计算右子树的高度
            } else {
                //左子树高度大于右子树高度，证明右子树肯定是满二叉树
                res += (1 << right) - 1;
                res += (countFullTreeNodes(root.left));
            }
            return res;
         }

        //满足完全二叉树的树，无论是不是满二叉树，最左路径长度都是其高度
        public int getSubTreeHeight(TreeNode root) {
            if (root == null) return 0;
            return getSubTreeHeight(root.left) + 1;
        }
    }

    @Test
    public void test1() {
        PostTraverse pt = new PostTraverse();
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        TreeNode cur = root.left;
        cur.left =  new TreeNode(3);
        cur.right = new TreeNode(4);
        cur = root.right;
        // cur.left = new TreeNode(5);
        // cur.right = new TreeNode(6);
        System.out.println(root.printTree());
        // System.out.println(pt.postOrder(root));
        // System.out.println(pt.postOrder1(root));
        System.out.println(new SerializeTree().serializeByLeverOrder(root));
        SerializeTree ser = new SerializeTree();
        root = ser.deserializeByLevelOrder(ser.serializeByLeverOrder(root));
        System.out.println(root.printTree());
        System.out.println(ser.serializeByPreOrder(root));
        root = ser.deserializeByPreOrder(ser.serializeByPreOrder(root));
        System.out.println(root.printTree());
        System.out.println(new JuageTree().isFullBinaryTree(root));
        System.out.println(new FullTreeCount().countFullTreeNodes(root));
    }

    //折纸问题，打印从上到下的折痕
    /* 
        规律：从第二次折叠开始，每次折叠会在上一个中间折痕的上面【无论中间折痕是“凹”还是“凸”】出现一个“凸”折痕，在下面出现一个“凹”折痕
        因为是从上往下，因此满足 边-中-边，即中序遍历
    */
    class PaperFold{
        public void printFoldedPaper(int times) {
            printByInOrder(0, "凹", times);
        }

        public void printByInOrder(int level, String cur, int max) {
            if (level == max) {
                //已经超过折叠次数，不再打印
                return;
            }
            printByInOrder(level + 1, "凸", max);
            System.out.println(cur);
            printByInOrder(level + 1, "凹", max);
        }
    }

    //通过二叉树递归套路解题
    class MaxDistance {
        //查询一棵树中的最大距离【距离：从某个节点以最短的方式达到另外一个节点】
        class Distace {

        }

        /* 
            什么样的信息：
            0：他能找到的最大距离，1：他的某个叶子结点到我的最远距离【即子树高度】
        */
        public int maxDistance (TreeNode root) {
            return postOrderFindMaxDistance(root)[0]; //只要root的最大距离即可
        }

        public int[] postOrderFindMaxDistance(TreeNode root) {
            if (root == null) return new int[]{0, 0};
            int[] left = postOrderFindMaxDistance(root.left), right = postOrderFindMaxDistance(root.right);
            int[] res = new int[2];
            //我的最远叶子结点到我父节点的距离从我左右子树的最远距离找
            res[1] = Math.max(left[1], right[1]) + 1;
            //我能得到的最大距离为左右子树提供给我的最大距离
            int max = left[0];
            //从最大信息中择优
            /* 
                候选方案：
                1. 从左子树得到他提供的最大距离，不做更改；【等价于左子树高度】
                2. 从右。。
                3. 将左子树最远叶子结点到我的距离 + 右子树。。。 + 我自己，就是一条通过我我的最大路径
            */
            max = Math.max(left[1] + right[1] + 1, Math.max(max, right[0]));
            res[0] = max;
            return res;
        }

//===================================================================================================================
    //case2：返回数中最大的二叉搜素树的头结点
    /* 
        列举可能性，想出所需要的信息：
        假设我是搜索二叉树，那我必须保证：
        1. 我的子树都是搜索二叉树【需要信息保存是否是BFT】
        2. 我得值大于左子树最大值，小于右子树最小值【需要信息保存左右子树的两个最值】
        此外，我需要知道左右子树的大小，以便计算我自己的大小【需要信息保存子树的大小】
        最后，我需要信息保存我自己的引用[需要保存树引用]

        假设我不是：
        可能是上述1,2中有一个不满足
        我只需找到左右子树中的最大子树，返回我的最大大小即可
    */
        class Info {
            TreeNode maxTree;
            boolean isBFT;
            int max;
            int min;
            int num;
            public Info(TreeNode maxTree, boolean isBFT, int max, int min, int num) {
                this.maxTree = maxTree;
                this.isBFT = isBFT;
                this.max = max;
                this.min = min;
                this.num = num;
            }
        }

        public TreeNode findMaxBFT(TreeNode root) {
            if (root == null) return root;
            return postOrderFindMaxBFT(root).maxTree;
        }

        public Info postOrderFindMaxBFT(TreeNode root) {
            //对于叶节点来说，肯定是BST
            if (root.left == null && root.right == null) return new Info(root, true, root.val, root.val, 1);
            Info left = postOrderFindMaxBFT(root.left), right = postOrderFindMaxBFT(root.right);

            //判断我是不是二叉平衡树
            boolean isBST = true;
            if (!left.isBFT || !right.isBFT || root.val < left.max || root.val > right.min) isBST = false;
            if (!isBST) {
                //如果我不是平衡二叉树，返回左右子树中的某一个最大的BST,并标记我自己不是BST
                Info maxInfo = left.num > right.num ? left : right;
                return new Info(maxInfo.maxTree, false, maxInfo.max, maxInfo.min, maxInfo.num);
            } else {
                //我是BST，我要将最大平衡子树修改为我自己，并返回我自己的数量及引用
                return new Info(root, true, right.max, left.min, left.num + right.num + 1);
            }
         }
    }

    class MultiTreeMethod {
        //员工类，整体呈现多叉树
        class Employee {
            public int happy;
            //子员工
            public List<Employee> subworker;
        }

        /* 
            1. 可以决定让某些员工来或者不来；
            2. 一旦某个有子员工的节点被选择，其子节点统统不能选择
            3. 选择一种选人方案，得到最大的happy值
        */

        /* 
            1. 选择当前节点；当前节点happy值加上
                只能从孙子节点获取信息，获取所有孙子节点选择或者不选择的最大值,累加
            2. 不选择当前节点：不要当前happy
                可以从子节点的选择与不选择中获取最大值 ，累加

                【可以知道，需要两个信息：1.选择当前，2.不选择当前。
                数据结构为整数对，可以使用int[]】
        */
        public int findMaxHappy(Employee root) {
            int[] res = findMaxHappyPostOrder(root);
            return Math.max(res[0], res[1]);
        }
        Map<Employee, int[]> map = new HashMap<>();
        public int[] findMaxHappyPostOrder(Employee root) {
            if (root == null) return new int[]{0, 0};
            if (map.containsKey(root)) return map.get(root);
            int[] res = new int[2];
            List<Employee> subs = root.subworker;
            //1. 不选择当前节点
            res[0] = 0;
            //2. 选择当前节点
            res[1] = root.happy;
            int[] subRes;
            for (int i = 0; i < subs.size(); i++) {
                subRes = findMaxHappyPostOrder(subs.get(i));
                //root不来：遍历所有子节点，从每种节点榨取最大值
                res[0] += Math.max(subRes[0], subRes[1]);
                //root来：只能得到每个子节点不来的快乐值
                res[1] += subRes[0];
            }    
            map.put(root, res);
            return res;
        }
    }

    //利用递归方法检查是否是完全二叉树
    class CheckFullBinaryTree {
        
        /* 
            当前节点参不参与？好像不空就得参与
            所需要的子树信息：int[]
            0:子树是不是完全二叉树?[用于提前返回] 是：1，不是0
            1:子树是不是满二叉树？[boolean] 是：1，不是0
            2:子树的高度
            //子树若有一个不是完全二叉树，直接返回继续返回false
            // 都是满的，查看高度是不是左 >= 右，一定是完全二叉树，直接返回高度； 若左 < 右，设置不是FBT，直接返回
            //有一个不是满的，查看是哪个
        */

        public boolean isFullBinaryTree(TreeNode root) {
            return isFullBinaryTreePostOrder(root)[0] == 1 ? true : false;
        }
        public int[] isFullBinaryTreePostOrder(TreeNode root) {
            //空树认为是满二叉树，也是完全二叉树
            if (root == null) return new int[]{1, 1, 0};
            int[] left = isFullBinaryTreePostOrder(root.left), right = isFullBinaryTreePostOrder(root.right);
            if (left[0] == 0 || right[0] == 0) return new int[]{0, 0, -1}; //不是，可以不用看了
            if (left[2] < right[2]) return new int[]{0, 0, -1}; //不是，可以不用看了
            int[] res = new int[3];
            //根据高度等或者不等做判断
            if (left[2] == right[2]) {
                //高度相等，必须保证左子树为满二叉树
                if (left[1] == 0) return new int[]{0, 0, -1}; //不是，可以不用看
            } else {
                //右子树较低，右子树必须为满二叉树
                if (left[1] == 0) return new int[]{0, 0, -1}; //不是，可以不用看了
            }
            res[2] = left[2] + 1; //高度通过检查
            res[0] = 1;
            //左右全是满二叉树，左子树、右子树高度相等，才是满二叉树
            res[1] = left[1] == 1 && right[1] == 1 && left[2] == right[2] ? 1 : 0;
            return res;
        }

    }

    //查找两个二叉树节点最低公共祖先
    class FindLowerCommonParents {
        /* 
            需要的信息：
            当前节点参与与否？很不幸，这不是当前节点所能决定的

            1. 若当前节点内**不含**两个节点中任何一个，不参与
            所需信息：（1）含有第一个节点否？(2)。。。二个。。。？ 【两个boolean】

            2. 含有其中一个
            可以传递给上层的信息：我肯定不是祖先【因此返回值还需一个是否是公共祖先？第三个boolean】
            但是我方有一个节点，上面两个boolean可以提供

            3. 含有其中两个
            子树各持有一个，那我就是；
            子树其中一个是公共祖先，返回子树 【这个判断应该尽量提前】
            【从这里可以看出，必须可以存储节点引用；
            根据前车之鉴，省去第三个boolean，**改为与左右子树比对或者是不是null**即可】
        */
        class Info {
            TreeNode coParent;
            boolean containsP;
            boolean containsQ;
            public Info(TreeNode coParent, boolean containsP, boolean containsQ) {
                this.coParent = coParent;
                this.containsP = containsP;
                this.containsQ = containsQ;
            }
        }
        public TreeNode findLowestCommonParent(TreeNode root, TreeNode p, TreeNode q) {
            return findLowestCommonParentPostOrder(root, p, q).coParent;
        }

        public Info findLowestCommonParentPostOrder1(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return new Info(null, false, false);
            Info left = findLowestCommonParentPostOrder1(root.left, p, q),
             right = findLowestCommonParentPostOrder1(root.right, p, q);
             if (left.coParent != null) return left; //左右当中有一个已经找到最低祖先，直接返回
             else if (right.coParent != null) return right;
             else {
                if (left.containsP && right.containsQ || left.containsQ && right.containsP)
                    return new Info(root, true, true); //左右子树分别含有P，Q我就是最低子树
                else if (root == p && (left.containsQ || right.containsP) ||
                root == q && (left.containsP || right.containsP)) 
                    return new Info(root, true, true); //我自己是P或者Q，且我的子树有另一个，我也是最低公共祖先
                else {
                    //只含有其中一个的情况
                    if (left.containsP || left.containsQ) return left;
                    else if (right.containsP || right.containsQ) return right;
                    else if (root == p) return new Info(null, true, false);
                    else if (root == q) return new Info(null, false, true);
                    else return left; //一无所有
                }
             }
        }

        public Info findLowestCommonParentPostOrder(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return new Info(null, false, false);
            Info left = findLowestCommonParentPostOrder(root.left, p, q),
             right = findLowestCommonParentPostOrder(root.right, p, q);
            TreeNode lowest = null;
            boolean hasP = false, hasQ = false;
             //设置两个布尔返回
            if (root == p || left.containsP || right.containsP) hasP = true;
            if (root == q || left.containsQ || right.containsQ) hasQ = true;
            //设置公共祖先返回
            if (left.coParent != null) lowest = left.coParent;
            if (right.coParent != null) lowest = right.coParent;
            if (lowest == null) {
                //若子树都没有，但是我此时却拥有P，Q，无论是什么情况，肯定是因为我的出现导致同时拥有了P，Q，因此我必定是公共祖先
                if (hasP && hasQ) lowest = root;
            }
            return new Info(lowest, hasP, hasQ);
        }
    }
    @Test
    public void test4() {
        TreeNode root =  TreeUtils.createTree(new Integer[]{9,3,11,12,14,null,15});
        TreeUtils.printBinaryTreeVisualization(root);
        // TreeNode res = new MaxDistance().findMaxBFT(root);
        Boolean res = new CheckFullBinaryTree().isFullBinaryTree(root);
        System.out.println(res);
    }
}
